package com.future;

import java.util.HashMap;
import java.util.Map;

/**
 * Description: 956. 最高的广告牌（大厂刷题22）
 *
 * @author weiruibai.vendor
 * Date: 2022/7/15 15:46
 */
public class Solution_956 {

    public static void main(String[] args) {
        int[] rods = new int[]{1, 2, 3, 6};
        rods = new int[]{1, 2, 3, 4, 5, 6};
        rods = new int[]{1, 2};
        rods = new int[]{3, 4, 3, 3, 2};
        rods = new int[]{61, 45, 43, 54, 40, 53, 55, 47, 51, 59, 42};
        System.out.println(tallestBillboard(rods));
    }

    public static int tallestBillboard(int[] rods) {
        if (rods == null || rods.length == 1) {
            return 0;
        }
        Map<Integer, Integer> oldMap = new HashMap<>();
        Map<Integer, Integer> curMap;
        // 开始时 k->0 v->0
        oldMap.put(0, 0);
        for (Integer num : rods) {
            curMap = new HashMap<>(oldMap);
            for (Integer key : curMap.keySet()) {
                /**
                 * key---差值
                 * value--较小值
                 * key+value--较大值
                 * 公式1：
                 */
                /**
                 * 较小值
                 */
                int differMore = curMap.get(key);
                /**
                 * 较大+num - 较小值
                 *
                 * newKey = 较大值加上+num - 较小值 =
                 *          (differMore+key)+num-differ = key+num
                 * newValue = 较小值 = differMore
                 */
                oldMap.put(key + num, Math.max(oldMap.getOrDefault(key + num, 0), differMore));
                /**
                 * 较小值+num - 较大
                 * newKey = differMore+num-(differMore+key)
                 * = num-key
                 * newValue = 较小值+newKey
                 *          = differMore+num-key
                 */
                int newKey = Math.abs(key - num);
                // 已经存在的值，不存在就是0
                int diffXD = oldMap.getOrDefault(newKey, 0);
                int newValue;
                if (key >= num) {
                    // differMore + num 较小值加上num是
                    newValue = Math.max(differMore + num, diffXD);
                } else {
                    // differMore + key 是较小值加上差值就是较大值
                    newValue = Math.max(differMore + key, diffXD);
                }
                oldMap.put(newKey, newValue);
            }
        }
        return oldMap.get(0);
    }
}
